package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Permutations {

    public static void main(String[] args) {
        Permutations permutations = new Permutations();
        List<List<Integer>> permute = permutations.permute(new int[]{1, 2, 3});
        permute.stream().forEach(System.out::println);
    }

    List<List<Integer>> list = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }
        dfs(output, 0, nums);
        return list;
    }

    public void dfs(List<Integer> res, int idx, int[] nums){
        if(idx == nums.length){
            list.add(new ArrayList<>(res));
        }
        for (int i = idx; i < nums.length; i++) {
            Collections.swap(res, idx, i);
            dfs(res, idx + 1, nums);
            Collections.swap(res, idx, i);
        }
    }

}
